package datastructure.array;

/**
 * http://www.leetcode.com/2011/03/median-of-two-sorted-arrays.html#comment-1053
 * http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
 * 
 * @author Lei
 */
public class FindMedianOfTwoSorrtedArray {

    public double findMedian(int A[], int B[], int l, int r, int nA, int nB) {
        if (l > r) {
            return findMedian(B, A, Math.max(0, (nA + nB) / 2 - nA), Math.min(nB, (nA + nB) / 2), nB, nA);
        }
        int i = (l + r) / 2;
        int j = (nA + nB) / 2 - i - 1;

        if (j >= 0 && A[i] < B[j]) {
            return findMedian(A, B, i + 1, r, nA, nB);
        }
        else if (j < nB - 1 && A[i] > B[j + 1]) {
            return findMedian(A, B, l, i - 1, nA, nB);
        }
        else {
            if ((nA + nB) % 2 == 1) {
                return A[i];
            }
            else if (i > 0) {
                return (A[i] + Math.max(B[j], A[i - 1])) / 2.0;
            }
            else {
                return (A[i] + B[j]) / 2.0;
            }
        }
    }
}
